package Hot_100;

import java.util.Scanner;

//岛屿数量
public class Hot_100_200 {
    /**
     * 主函数
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //初始化字符数组
      char ch[][]=new char[][]{
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'},
        };
        //调用处理函数并输出结果
        System.out.println(numIslands(ch));
    }

    /**
     * 求岛屿数量
     *
     * @param grid
     * @return
     */
    public static int numIslands(char [][] grid) {
        int ans = 0;
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j]=='1') {
                    ans++;
                    dfs(grid, i, j);
                }
            }
        return ans;
    }

    /**
     * dfs
     *
     * @param grid
     * @param i
     * @param j
     */
    public static void dfs(char[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return;
        }
        if (grid[i][j]=='0') {
            return;
        }
        grid[i][j]= '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}
//时间复杂度: O(n^2)
//空间复杂度: O(1)